/**
 * 69. x 的平方根
 */

class Solution1 {
    public int mySqrt(int x) {
      long tmp = 0;//防止越界
        for (int i = 1;i<=x;i++){
            long n = (long)i*i;
            if (n > x){
                break;
            }
            tmp = i;
        }
        return (int)tmp;
    }

    /**
     *      二分查找法
     * @param x
     * @return
     */
    public int mySqrt2(int x) {
        if (x == 0 || x == 1) return x;
        int tmp = 0;
        int left = 1;
        int right = x-1;
        while (left <= right){
            int mid = (left + right)/2;
            if ((long)mid * mid <= x){
                tmp = mid;
                left = left + 1;
            }else{
                right = mid - 1;
            }
        }
        return tmp;
    }
}


/**
 * 70. 爬楼梯
 */
class Solution2 {
    public int climbStairs(int n) {
        if (n == 0 || n == 1 || n == 2){
            return n;
        }
        int a = 1;
        int b = 2;
        int tmp = 0;
        for (int i = 3;i<= n;i++){
            tmp = a+b;
            a = b;
            b = tmp;

        }
        return tmp;
    }
}


/**
 * 88. 合并两个有序数组
 */
class Solution3 {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if (n == 0) return;
        int n1 = m-1;
        int n2 = n-1;
        int k = m+n-1;
        while (n1 >=0 && n2 >= 0){
            if ( nums2[n2] > nums1[n1] ){
                nums1[k] = nums2[n2];
                n2--;
            }else{
                nums1[k] = nums1[n1];
                n1--;
            }
            k--;
        }
        if (n1 != 0){
            nums1[k] = nums1[n1];
            n1--;
            k--;
        }
        if (n2 != 0){
            nums1[k] = nums1[n2];
            n2--;
            k--;
        }
    }
}


/**
 * 125. 验证回文串
 */
class Solution4 {
    public boolean isPalindrome(String s) {
        s.trim();
        s = s.toLowerCase();
        int len = s.length();
        StringBuilder str = new StringBuilder();
        for (char ch : s.toCharArray()){
            if((ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9')){
                str.append(ch);
            }
        }
        ;
        //比较去掉符号后的字符串
        return str.toString().equals(str.reverse().toString());
    }
}

/**
 * 136. 只出现一次的数字
 */
class Solution5 {

    /**
     *                暴力求解
     * @param nums
     * @return
     */
    public int singleNumber(int[] nums) {
        //int[] hash = new int[nums.length];
        for (int i = 0;i<nums.length;i++){
            int flag = 1;
            for (int j = 0;j<nums.length;j++){
                if (i != j){
                    if (nums[i] != nums[j]){
                        flag = 1;
                    }else if (nums[i] == nums[j]){
                        flag = 0;
                        break;
                    }
                }

            }
            if (flag == 1){
                return nums[i];
            }
        }

        return 0;
    }

    /**
     *      异或 == 找不同
     * @param nums
     * @return
     */

    public int singleNumber2(int[] nums) {
        //int[] hash = new int[nums.length];
        int ans = 0;
        for (int i = 0;i<nums.length;i++){
            ans ^= nums[i];
        }

        return ans;
    }
}